МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” ІНСТИТУТ КОМП’ЮТЕРНИХ НАУК ТА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ Кафедра “Системи автоматизованого проектування”
ЗВІТ до лабораторної роботи №6 на тему «ДОСЛІДЖЕННЯ АЛГОРИТМІВ РОЗПІЗНАВАННЯ ОБРАЗІВ.ЗАДАЧА ВИЗНАЧЕННЯ КОЕФІЦІЄНТІВ ЛРФ ДЛЯ КІЛЬКОХ МНОЖИН ОБРАЗІВ» з курсу «Системи штучного інтелекту»  Львів-2008 1.Мета роботи Вивчити принципи алгоритмів побудови лінійних рішаючих функцій для кількох класів. Написати програму реалізації алгоритму з графічним інтерфейсом користувача. Короткі теоретичні відомості 2.1. Машина перцептрона. Перцептронний підхід до розпізнавання образів Структура машини перцептрона була запропонована у 1957 році як модель машини, здатної до навчання. Рис. 1. Структура машини перцептрона Ця машина складається з наступних частин: Сенсори (давачі), які сприймають зовнішню інформацію Асоціативний шар. Кожен давач з'єднаний з кожним блоком асоціативного шару. Виходом цього шару є ознаки
. Блок вагових коефіціентів. За допомогою цього блоку ознаки зважуються (
). Загальний суматор - в ньому отримується значення реакції
. Блок рішення - сюди поступає значення реакції із загального суматора. По значенню
визначається налажність образу до того чи іншого класу. Якщо поступає образ класу
(
), а на виході отримується
тоді коректуються вагові коефіціенти. Значення вектора
вважається знайденим правильно, якщо для будь-яких образів з класів
і
класифікація відбувається правильно. Така машина є типовою архітектурою машини із здатністю до самонавчання. Алгоритм роботи машини перцептрона грунтується на ідеї "заохочення-покарання". Робота починається з де-якого початкового наближення
. Нехай ми знаходимось на k-ому кроці і нехай ми перевіряємо якийсь k-ий образ з множини вибірки
. Припустимо, що ми розглядаємо лінійну рішаючу функцію для двох класів
і
, причому значення лінійної рішаючої функції в класі
більше нуля, а в класі
- менше нуля. На k-ому кроці ми перевіряємо значення лінійної рішаючої функції для заданого вектора
, причому
. Якщо виконується умова
тоді ніяких корекцій вагових коефіцентів робити непотрібно. Якщо ж
тоді потрібно здійснювати корекцію вагових коефіцентів. Вона здійснюється за наступним алгоритмом:
, де
- коректуючий приріст В більшості випадків приймають
. Якщо ми вибираємо вектор
з області
тоді перевіряємо значення
. Якщо
тоді ніяких корекцій вагових коефіцентів робити непотрібно. Якщо ж
тоді корекція здійснюється за наступним правилом:
Вагові коефіціенти вважаються знайденими правильно, якщо для всіх образів, що належать класам
і
правильно визначається знак лінійної рішаючої функції. Існують наступні варіанти вибору коректуючого приросту
: Алгоритм фіксованого приросту:
,
Алгоритм корекції абсолютної величини:
- по цій різниці здійснюють оцінку параметра
.
,
,
Алгоритм дробової корекції:
- найбільше ціле число, яке не перевищує
. Алгоритм перцептрона збіжний лише в отму випадку, коли класи лінійно розділимі. Якщо ж класи лінійно нерозділимі, тоді алгоритм перцептрона зациклюється. 2.2. Процедура навчання класифікаторів для декількох класів Нехай ми маємо
класів. Тоді на k-ому кроці навчання в систему поступає образ
, обчислюється
значень лінійних рішаючих функцій:
Припустимо, що
. Тоді, якщо виконується умова
для будь-якого
, тоді корекції вагових коефіціентів здійснювати непотрібно, тобто
. Нехай для деякого


тоді потрібно виконати наступну корекцію:
для всіх решта векторів вагових коефіціентів
. Якщо класи лінійно розмежовані, тоді цей алгоритм збігається. 2.3. Вибір математичної моделі Для простоти будемо розглядати двовимірний випадок, тобто вектор ознак
є двокомпонентним. Також необхідно вибрати спосіб за яким буде визначатись належність образу до того чи іншого класу. Виберемо наступний варіант:
, тоді
. При проведенні корекції вектора вагових коефіціентів використовується ...